#include <iostream>
#include <vector>
#include <string>
using namespace std;

void IterDo(int curi, bool *ver, bool *hor, bool *slash, bool *bslash, int n, int *ires, int &res){
    if(curi == n){
        // append output
        ++res;
    }
    for(int i=0; i<n; ++i){
        // try every point
        // test if it can put
        int putVer = i;
        int putHor = curi;
        int putSlash = putVer + putHor;
        int putBslash = n - 1 - putVer + putHor;
        if(!ver[putVer] && !hor[putHor] && !slash[putSlash] && !bslash[putBslash]){
            // put it
            ver[putVer] = true;
            hor[putHor] = true;
            slash[putSlash] = true;
            bslash[putBslash] = true;
            ires[curi] = i;
            // IterDo
            IterDo(curi+1, ver, hor, slash, bslash, n, ires, res);
            // draw back
            ver[putVer] = false;
            hor[putHor] = false;
            slash[putSlash] = false;
            bslash[putBslash] = false;
        }
    }
}


int solveNQueens(int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int res = 0;
    if(n==1){
        return 1;
    }

    if(n<4)
        return res;
    bool *ver = new bool[n];
    bool *hor = new bool[n];
    bool *slash = new bool[2*n];
    bool *bslash = new bool[2*n];
    int *ires = new int[n];
    // init
    for(int i=0; i<n; ++i){
        ver[i] = false;
        hor[i] = false;
    }
    for(int i=0; i<2*n; ++i){
        slash[i] = false;
        bslash[i] = false;
    }
    // go
    IterDo(0, ver, hor, slash, bslash, n, ires, res);

    return res;

}

int main()
{

    return 0;
}